package xyf.p02.stack_queue;

import java.util.Stack;

/**
 * ClassName: P0042_Trap
 * Description:
 * Author: xyf
 * Date: 9/7/22 7:47 PM
 * Version: 1.0
 **/
public class P0042_Trap
{
    public int trap(int[] height)
    {
        int[] left = new int[height.length];

        int[] right = new int[height.length];

        left[0] = 0;
        for (int i = 1; i < height.length; i++)
        {
            left[i] = Math.max(height[i - 1], left[i - 1]);
        }

        right[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--)
        {
            right[i] = Math.max(height[i + 1], right[i + 1]);
        }

        int max = 0;

        for (int i = 0; i < height.length; i++)
        {
            int cur = Math.min(left[i], right[i]) - height[i];

            max += cur < 0 ? 0 : cur;
        }
        return max;
    }
}